package com;

/**
 * https://leetcode-cn.com/problems/add-two-numbers/
 * 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
 * <p>
 * 请你将两个数相加，并以相同形式返回一个表示和的链表。
 * <p>
 * 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/add-two-numbers
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author 罗俊华
 * @date 2021/7/22 - 1:27 下午
 */
public class AddToNum {

    public static void main(String[] args) {

        int[] l1 = {2, 4, 9};
        int[] l2 = {5, 6, 4, 9};


        ListNode listNode = new Solution().addTwoNumbers(toListNode(l1), toListNode(l2));

        while (listNode != null) {
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }


    private static ListNode toListNode(int[] l) {

        ListNode root = new ListNode();
        ListNode temp = root;
        for (int i = 0; i < l.length; i++) {
            temp.next = new ListNode(l[i]);
            temp = temp.next;
        }
        return root.next;
    }

}

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        ListNode sentinel = new ListNode();

        addByBit(l1, l2, sentinel);

        return sentinel.next;
    }

    private ListNode addByBit(ListNode l1, ListNode l2, ListNode lastNode) {
        ListNode currentNode = null;
        // 进位
        int carry = carryOn(lastNode);

        if (l1 != null && l2 != null) {
            currentNode = new ListNode(l1.val + l2.val + carry);

            lastNode.next = currentNode;
            return addByBit(l1.next, l2.next, currentNode);
        } else if (l1 == null && l2 == null) {

            if (carry != 0) {
                lastNode.next = new ListNode(carry);
            }

            return null;
        } else if (l1 == null) {
            currentNode = new ListNode(l2.val + carry);

            lastNode.next = currentNode;
            return addByBit(l1, l2.next, currentNode);
        } else /*if (l2 == null)*/ {
            currentNode = new ListNode(l1.val + carry);

            lastNode.next = currentNode;
            return addByBit(l1.next, l2, currentNode);
        }


    }

    private int carryOn(ListNode child) {
        // 进位
        int carry = child.val / 10;

        child.val = child.val % 10;
        return carry;
    }
}

/**
 * 读错题目
 */
class Solution1 {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        int l1Size = 0;
        int l2Size = 0;
        ListNode l1t = l1;
        while (l1t != null) {
            l1Size++;
            l1t = l1t.next;
        }
        ListNode l2t = l2;

        while (l2t != null) {
            l2Size++;
            l2t = l2t.next;
        }

        ListNode head = new ListNode();
        ListNode child = null;
        if (l2Size > l1Size) {

            child = addByBit(l2, l1, l2Size, l1Size, 0, head);

        } else {
            child = addByBit(l1, l2, l1Size, l2Size, 0, head);

        }

        int carry = carryOn(child);

        if (carry != 0) {
            child.next = new ListNode(carry);
        }
        return head;

    }

    private ListNode addByBit(ListNode l1, ListNode l2, final int l1Size, final int l2Size, final int currentIndex, ListNode head) {

        ListNode child = null;

        if (l1Size - currentIndex > l2Size) {

            child = addByBit(l1.next, l2, l1Size, l2Size, currentIndex + 1, head);

            int carry = carryOn(child);

            ListNode father = new ListNode(l1.val + carry);

            child.next = father;

            return father;

        } else if (l1.next != null && l2.next != null) {

            child = addByBit(l1.next, l2.next, l1Size, l2Size, currentIndex + 1, head);

            // 进位
            int carry = carryOn(child);

            ListNode father = new ListNode(l1.val + l2.val + carry);

            child.next = father;

            return father;

        } else if (l1.next == null && l2.next == null) {
            head.val = l1.val + l2.val;
            return head;
        }

        return null;

    }

    private int carryOn(ListNode child) {
        // 进位
        int carry = child.val / 10;

        child.val = child.val % 10;
        return carry;
    }
}

// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

